//package linkedlist;
//
//class Node {
//    int val;
//    Node next;
//    Node random;
//    public Node(int val) {
//        this.val = val;
//        this.next = null;
//        this.random = null;
//    }
//}
//public class no138 {
//    public Node copyRandomList(Node head) {
//        Node cur = head;
//        if(head == null){
//            return null;
//        }
//        while (cur != null){
//            Node node = new Node(cur.val);
//            node.next = cur.next;
//            cur.next = node;
//            cur = node.next;
//        }
//        cur = head;
//        while (cur != null){
//             Node prev = cur.next;
//             if (cur.random != null){
//                 prev.random = cur.random.next;
//             }
//             cur = cur.next.next;
//        }
//        cur = head;
//        Node newNode = new Node(-1);
//        Node temp = newNode;
//        while (cur != null){
//            temp.next = cur.next;
//            temp = temp.next;
//            cur.next = temp.next;
//            cur = cur.next;
//        }
//        return newNode.next;
//    }
//}
